#define K_HASH_INITSIZE 83

typedef uintptr_t   hashcode_t;
typedef struct hentry_t {
    hashcode_t hcode;
    struct hentry_t *next;
    union {
        js_string_t     *skey;
        void     *key;
    };
    union {
        js_object_t     *value;
        uintptr_t        nvalue;
    };
} hentry_t;

typedef struct hmap_t {
    hentry_t *arena;
    hentry_t *unused;
    hentry_t **hentry;
    size_t arenasize;
    size_t size;
    size_t hmax;
    size_t stat_total;
    size_t stat_hit;
} hmap_t;
typedef void mapptr_t;
typedef struct PtrMap_t {
    js_header h;
    hentry_t *e;
    mapptr_t   *mapptr;
} PtrMap_t ;

static inline hashcode_t hash(hashcode_t h, const char *p, size_t len)
{
    size_t i;
    for(i = 0; i < len; i++) {
        h = p[i] + 31 * h;
    }
    return h;
}

static void hmap_setfreelist(hmap_t *hmap, size_t s, size_t e)
{
    bzero(hmap->arena + s, (e - s) * sizeof(hentry_t));
    hmap->unused = hmap->arena + s;
    size_t i;
    for(i = s; i < e - 1; i++) {
        hmap->arena[i].hcode = ((hashcode_t)-1);
        hmap->arena[i].nvalue = 0;
        hmap->arena[i].next = hmap->arena + i + 1;
    }
    hmap->arena[e-1].hcode = ((hashcode_t)-1);
    hmap->arena[e-1].nvalue = 0;
}

static void hmap_rehash(hmap_t *hmap)
{
    size_t i, newhmax = hmap->hmax * 2 + 1;
    hentry_t **newhentry = MALLOC(hentry_t**, newhmax * sizeof(hentry_t*));
    bzero(newhentry, newhmax * sizeof(hentry_t*));
    for(i = 0; i < hmap->arenasize / 2; i++) {
        hentry_t *e = hmap->arena + i;
        hashcode_t ni = e->hcode % newhmax;
        e->next = newhentry[ni];
        newhentry[ni] = e;
    }
    FREE(hmap->hentry, hmap->hmax * sizeof(hentry_t*));
    hmap->hentry = newhentry;
    hmap->hmax = newhmax;
}

static void hmap_shiftptr(hmap_t *hmap, intptr_t shift)
{
    size_t i, size = hmap->arenasize / 2;
    for(i = 0; i < size; i++) {
        hentry_t *e = hmap->arena + i;
        if(e->next != NULL) {
            e->next = (hentry_t*)(((char*)e->next) + shift);
        }
    }
}

static hentry_t *new_hentry(hmap_t *hmap, hashcode_t hcode)
{
    hentry_t *e;
    if(hmap->unused == NULL) {
        size_t oarenasize = hmap->arenasize;
        char *oarena = (char*)hmap->arena;
        hmap->arenasize *= 2;
        hmap->arena = REALLOC(hentry_t*, hmap->arena, hmap->arenasize*sizeof(hentry_t));
        if((void*)hmap->arena != oarena) {
            hmap_shiftptr(hmap, (char*)hmap->arena - oarena);
        }
        hmap_setfreelist(hmap, oarenasize, hmap->arenasize);
        hmap_rehash(hmap);
    }
    e = hmap->unused;
    hmap->unused = e->next;
    e->hcode = hcode;
    e->next = NULL;
    hmap->size++;
    return e;
}

static mapptr_t *hmap_init(size_t init)
{
    hmap_t *hmap = MALLOC(hmap_t*, sizeof(hmap_t));
    bzero(hmap, sizeof(hmap_t));
    if(init < K_HASH_INITSIZE) init = K_HASH_INITSIZE;
    hmap->arenasize = (init * 3) / 4;
    hmap->arena = MALLOC(hentry_t*, hmap->arenasize * sizeof(hentry_t));
    hmap_setfreelist(hmap, 0, hmap->arenasize);
    hmap->hentry = MALLOC(hentry_t**, init * sizeof(hentry_t*));
    bzero(hmap->hentry, init * sizeof(hentry_t*));
    hmap->hmax = init;
    hmap->size = 0;
    return (mapptr_t*)hmap;
}

static void hmap_free(mapptr_t *m)
{
    hmap_t *hmap = (hmap_t*)m;
    FREE(hmap->arena, sizeof(hentry_t)*(hmap->arenasize));
    FREE(hmap->hentry, sizeof(hentry_t*)*(hmap->hmax));
    FREE(hmap, sizeof(hmap_t));
}

static hentry_t *hmap_getentry(hmap_t* hmap, hashcode_t hcode)
{
    hentry_t **hlist = hmap->hentry;
    size_t idx = hcode % hmap->hmax;
    hentry_t *e = hlist[idx];
    while(e != NULL) {
        if(e->hcode == hcode) return e;
        e = e->next;
    }
    return NULL;
}

static void hmap_add(hmap_t* hmap, hentry_t *ne)
{
    hentry_t **hlist = hmap->hentry;
    size_t idx = ne->hcode % hmap->hmax;
    ne->next = hlist[idx];
    hlist[idx] = ne;
}

static void hmap_remove(hmap_t* hmap, hentry_t *oe)
{
    hentry_t **hlist = hmap->hentry;
    size_t idx = oe->hcode % hmap->hmax;
    hentry_t *e = hlist[idx];
    while(e != NULL) {
        if(e->next == oe) {
            e->next = oe->next;
            return;
        }
        e = e->next;
    }
    hlist[idx] = oe->next;
}

PtrMap_t* new_PtrMap(size_t max)
{
    PtrMap_t *m = NEW(PtrMap_t);
    m->mapptr = hmap_init(max);
    return (PtrMap_t*)m;
}

static void hmap_top(hmap_t* hmap, hentry_t *oe)
{
    hentry_t **hlist = hmap->hentry;
    size_t idx = oe->hcode % hmap->hmax;
    if(hlist[idx] != oe) {
        hmap_remove(hmap, oe);
        oe->next = hlist[idx];
        hlist[idx] = oe;
    }
}

void* PtrMap_get(PtrMap_t *pm, void *keyptr)
{
    hmap_t *hmap = (hmap_t*)pm->mapptr;
    hashcode_t hcode = (hashcode_t)keyptr;
    hentry_t *e = hmap_getentry(hmap, hcode);
    if(e != NULL) {
        hmap_top(hmap, e);
        return e->value;
    }
    return NULL;
}

void PtrMap_add(PtrMap_t *pm, void *keyptr, void *valueptr)
{
    hmap_t *hmap = (hmap_t*)pm->mapptr;
    hashcode_t hcode = (hashcode_t)keyptr;
    hentry_t *e = new_hentry(hmap, hcode);
    e->value = valueptr;
    hmap_add(hmap, e);
}

void PtrMap_rm(PtrMap_t *pm, void *keyptr)
{
    hmap_t *hmap = (hmap_t*)pm->mapptr;
    hashcode_t hcode = (hashcode_t)keyptr;
    hentry_t *e = hmap_getentry(hmap, hcode);
    hmap_remove(hmap, e);
    hmap_unuse(hmap, e);
}

size_t PtrMap_size(PtrMap_t *pm)
{
    hmap_t *hmap = (hmap_t*)pm->mapptr;
    return hmap->size;
}

void PtrMap_stat(PtrMap_t *pm, const char *name)
{
    hmap_t *hmap = (hmap_t*)pm->mapptr;
    if(hmap->stat_total > 9) {
        logprintf("STAT", isVerbosePref(), "size=%lu, name=%s count=%d %f%%", hmap->size, name, hmap->stat_total, 100.0 * hmap->stat_hit / hmap->stat_total);
        //		LOGSFPDATA = {sDATA("name", name), /*fDATA("rate", hmap->stat_hit / hmap->stat_total),*/ iDATA("count", hmap->stat_total)};
        //		LIB_STAT("konoha.PtrMap");
    }
}

js_string_t* PtrMap_getS(PtrMap_t *pm, const char *k, size_t len)
{
    hmap_t *hmap = (hmap_t*)pm->mapptr;
    hashcode_t hcode = hash(0, k, len);
    hentry_t *e = hmap_getentry(hmap, hcode);
    hmap->stat_total++;
    while(e != NULL) {
        const char *es = (const char*)e->key;
        if(e->hcode == hcode && es[len] == 0 && strncmp(k, es, len) == 0) {
            hmap->stat_hit++;
            return (js_string_t*)e->value;
        }
        e = e->next;
    }
    return NULL;
}

void PtrMap_addS(PtrMap_t *pm, js_string_t *ks, void *v)
{
    hmap_t *hmap = (hmap_t*)pm->mapptr;
    const char *k = (ks)->__str;
    size_t len = (ks)->length;
    hashcode_t hcode = hash(0, k, len);
    hentry_t *e = new_hentry(hmap, hcode);
    e->key = (void*)k;
    e->value = v;
    hmap_add(hmap, e);
}


